package com.practice.merge;

import java.util.ArrayList;
import java.util.PriorityQueue;

/**
 * Definition for singly-linked list.
 */
class ListNode {
	int val;
	ListNode next;

	ListNode(int x) {
		val = x;
		next = null;
	}
}

class Pair implements Comparable {
	public int first;
	public int second;

	public Pair(int first, int second) {
		this.first = first;
		this.second = second;
	}

	public int compareTo(Object o) {
		Pair other = (Pair) o;
		if (this.first > other.first) {
			return 1;
		} else if (this.first < other.first) {
			return -1;
		}
		return 0;
	}
}

public class Solution {
	public ListNode mergeKLists(ArrayList<ListNode> lists) {
		ListNode dummy = new ListNode(0);
		ListNode head = dummy;
		PriorityQueue q = new PriorityQueue();
		// initialize heap with first element from each list
		int k = lists.size();
		for (int i = 0; i < k; i++) {
			if (lists.get(i) != null) {
				q.add(new Pair(lists.get(i).val, i));
			}
		}

		Object o;
		while ((o = q.poll()) != null) {
			int i = ((Pair) o).second;
			ListNode c = lists.get(i);
			dummy.next = c;
			dummy = dummy.next;
			lists.set(i, c.next);
			if (c.next != null) {
				q.add(new Pair(c.next.val, i));
			}
		}

		return head.next;
	}
}